#include <stack>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};


class Solution {
private:
    bool is_same(TreeNode* t1, TreeNode* t2) {
        if (t1 == nullptr && t2 == nullptr) {
            return true;
        } else if (t1 == nullptr || t2 == nullptr || t1->val != t2->val) {
            return false;
        }
        return is_same(t1->left, t2->left) && is_same(t1->right, t2->right);
    }
public:
    bool isSubtree(TreeNode* s, TreeNode* t) {
        TreeNode* node = s;
        stack<TreeNode*> stack;
        while (true) {
            if (is_same(node, t)) {
                return true;
            }
            if (node->right != nullptr) {
                stack.push(node->right);
            }
            if (node->left != nullptr) {
                node = node->left;
            } else if (node->left == nullptr) {
                if (stack.empty()) {
                    return false;
                } else {
                    node = stack.top();
                    stack.pop();
                }
            }
        }
        return false;
    }
};